'''
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
'''

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        #记录路径
        track = []
        #「路径」中的元素会被标记为 true，避免重复使用
        used = [False] * len(nums)
        res = []

        def backtrack(nums,track,used):
            #触发结束条件
            if len(track) == len(nums):
                return res.append(track.copy())
            
            for i in range(len(nums)):
                
                #排除不合法的选择
                if used[i]:
                    continue
                #做选择
                track.append(nums[i])
                used[i] = True
                #进入下一层决策树
                backtrack(nums,track,used)
                #取消选择
                track.pop()
                used[i] = False

        backtrack(nums,track,used)
        return res






        